README.md

220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0 Output: true 

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2 Output: true 

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false 

Solutions (Rust)

1. Linear Scan-k first

implSolution{pubfncontains_nearby_almost_duplicate(nums:Vec<i32>,k:i32,t:i32) -> bool{let k = k asusize;let t = t asi64;let len = nums.len();let nums:Vec<i64> = nums.iter().map(|x| *x asi64).collect();for i in0..len {for n in&nums[(i + 1)..len.min(i + 1 + k)]{if(nums[i] - n).abs() <= t {returntrue;}}}false}}

2. Linear Scan-t first

implSolution{pubfncontains_nearby_almost_duplicate(nums:Vec<i32>,k:i32,t:i32) -> bool{letmut len = nums.len();letmut v = Vec::new();for i in0..len { v.push((nums[i]asi64, i asi32));} v.sort_unstable();for i in0..len {letmut j = i + 1;while j < len && v[j].0 - v[i].0 <= t asi64{if(v[j].1 - v[i].1).abs() <= k {returntrue;} j += 1;}}false}}

3. TreeMap

use std::collections::BTreeSet;implSolution{pubfncontains_nearby_almost_duplicate(nums:Vec<i32>,k:i32,t:i32) -> bool{if t < 0{returnfalse;}let k = k asusize;let t = t asi64;let nums:Vec<i64> = nums.iter().map(|x| *x asi64).collect();letmut tree = BTreeSet::new();for i in0..nums.len(){let n = nums[i];if tree.range((n - t)..=(n + t)).count() > 0{returntrue;} tree.insert(n);if i >= k { tree.remove(&nums[i - k]);}}false}}

4. Bucket

use std::collections::HashMap;implSolution{pubfncontains_nearby_almost_duplicate(nums:Vec<i32>,k:i32,t:i32) -> bool{if t < 0{returnfalse;}let k = k asusize;let t = t asi64;let nums:Vec<i64> = nums.iter().map(|x| *x asi64).collect();letmut buckets = HashMap::new();for i in0..nums.len(){let bucket_id = (nums[i]asf64 / (t + 1)asf64).floor()asi64;if buckets.insert(bucket_id, nums[i]) != None{returntrue;}match buckets.get(&(bucket_id - 1)){Some(n) => {if(n - nums[i]).abs() <= t {returntrue;}},None => (),}match buckets.get(&(bucket_id + 1)){Some(n) => {if(n - nums[i]).abs() <= t {returntrue;}},None => (),}if i >= k { buckets.remove(&(nums[i - k] / (t + 1)));}}false}}